79. 单词搜索

链接：https://leetcode-cn.com/problems/word-search/

题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]

给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.

分析

class Solution(object):
    def __init__(self):
        self.result = None
        # 小技巧分别表示左下右上
        self.directs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        self.visited = None
        # 分别表示边界
        self.m = 0
        self.n = 0

    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        self.visited = [[0] * len(board[0]) for _ in range(len(board))]
        self.m = len(board)
        self.n = len(board[0])

        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] != word[0]:
                    continue
                if self.dfs(board, word, 0, i, j):
                    return True
        return False

    def dfs(self, board, word, n, x, y):
        # 递归边界
        if n == len(word) - 1:
            return word[n] == board[x][y]

        if board[x][y] == word[n]:
            self.visited[x][y] = 1
            for i in range(4):
                # 得到新位置
                new_x, new_y = x + self.directs[i][0], y + self.directs[i][1]
                # 沿着某个方向走 发现不对跳出
                if self.in_area(new_x, new_y) and self.visited[new_x][new_y] == 0:
                    if self.dfs(board, word, n + 1, new_x, new_y):
                        return True
            self.visited[x][y] = 0
        return False

    def in_area(self, x, y):
        return 0 <= x < self.m and 0 <= y < self.n